package array;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BatteryCapacity {

	/*
	 * -ve number represents ascent i.e. loss in energy during ascent
	 * +ve number represents descent i.e. gain in energy during descent
	 * 
	 * Robot starts with the full capacity and any gain during descent is
	 * limited by battery capacity
	 *  
	 * */
	public static int calculateBatteryCapacity(int[] arr){

		// consolidate contiguous ascents and descents
		// e.g. for arr = {-12, 26, -14, -19, -1, 2, 3, 1, 23, 6, -20, 11, 18, -28, 28, -5, -29, 0, -11, 22}
		// streaks will be = {-12, 26, -34, 35, -20, 29, -28, 28, -45, 22}
		List<Integer> streaks = new ArrayList<Integer>();
		int positive = 0;
		int negative = 0;
		boolean isPositive = false;

		for(int index = 0; index < arr.length; index++){

			if(arr[index] == 0) continue;

			isPositive = arr[index] >= 0 ? true : false;

			if(isPositive){
				if(negative < 0) streaks.add(negative);
				negative = 0;
				positive = positive + arr[index];
			}else{
				if(positive > 0) streaks.add(positive);
				positive = 0;
				negative = negative + arr[index];
			}
		}

		if(positive > 0) streaks.add(positive);
		if(negative < 0) streaks.add(negative);

		//System.out.println("\nList: "+streaks);

		// reverse the values for the calculation
		Collections.reverse(streaks);
		// if last value in the streaks is +ve (descent), it won't make any change for capacity to be calculated
		// so discard it right away for simplicity e.g. in reversed streaks {22, -45, 28, -28, 29, -20, 35, -34, 26, -12}
		// 22 will be discarded
		if(streaks.get(0) > 0) streaks.remove(0); // this will fail in case like arr = {0,0,0} 

		int currentNegative = 0; // current ascent (it's a negative number in streaks)
		int currentPositive = 0; // current descent (it's a positive number in streaks)
		int currentCapacity = 0; // variable to keep capacity at a particular time in computation
		int currentEnergyDeficit = 0;
		int expectedAdditionalEnergyAfterPreviousDescent = 0;

		// take each pair of descent and ascent
		// e.g. for reversed streaks {-45, 28, -28, 29, -20, 35, -34, 26, -12}, the pairs 
		// "-45, 28", "-28, 29", "-20, 35", "-34, 26", "-12, 0" will participate in iteration in this order
		for(int index = 0; index < streaks.size();){
			currentNegative = streaks.get(index);
			if(index+1 < streaks.size()){
				currentPositive = streaks.get(index+1);
			}else{
				currentPositive = 0;
			}

			// calculation will start at each pair and will maintain current min capacity required.
			// current min capacity will be at least the amount of energy required for ascent plus
			// additional energy in case preceding descent didn't provide enough energy
			if((-currentNegative + expectedAdditionalEnergyAfterPreviousDescent) > currentCapacity){
				currentCapacity = -currentNegative + expectedAdditionalEnergyAfterPreviousDescent;
			} 

			// if preceding descent doesn't generate enough energy for succeeding ascent, it's termed as energy deficit
			// and it's passed to next iteration to be accounted in currentCapacity of next iteration.
			// Please note as the input has been reversed, calculation is in fact running from the end to
			// start point of the robot's given path. hence, in the end of the for loop, it'll generate how much 'optimum'
			// battery capacity, a robot should start with 
			currentEnergyDeficit = currentPositive + currentNegative - expectedAdditionalEnergyAfterPreviousDescent;
			if(currentEnergyDeficit < 0){
				expectedAdditionalEnergyAfterPreviousDescent = -currentEnergyDeficit;
			}else{
				expectedAdditionalEnergyAfterPreviousDescent = 0; // if current iteration takes care of energy deficits
				// created so far, no need to pass it further
			}

			index += 2;
		} // end of for loop

		// optimum capacity so that robot can finish its path
		return currentCapacity;
	}

}
